/*
 * @lc app=leetcode.cn id=990 lang=c
 *
 * [990] 等式方程的可满足性
 */

// @lc code=start
int set[26];

int find(int x) {
    if (set[x] != x){
        set[x] = find(set[x]);
    }
    return set[x];
}

void uTwo(int a, int b) {
    int _a = find(a);
    int _b = find(b);
    if (_a != _b) {
        set[_a] = _b;
    }
}

bool equationsPossible(char ** equations, int equationsSize){
    for (int i = 0; i < 26; ++i) {
        set[i] = i;
    }

    for (int i = 0; i < equationsSize; ++i) {
        if (equations[i][1] == '=') {
            int a = (int)(equations[i][0] - 'a');
            int b = (int)(equations[i][3] - 'a');        
            uTwo(a, b);
        }
    }
    for (int i = 0; i < equationsSize; ++i) {
        if (equations[i][1] == '!') {
            int a = (int)(equations[i][0] - 'a');
            int b = (int)(equations[i][3] - 'a');      
            if (find(a) == find(b)) {
                return false;
            }
        }
    }
    return true;
}
// @lc code=end

